package QuestionDaily;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class minimumTotalPrice_2646 {

    private List<Integer>[] g;
    private int[] price, cnt;
    private int end;

    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        /**
         * 真没思路啊，这种规划路径的题
         * 看高解思路
         * 每个 trips[i] 都 DFS 一次这棵树
         * 在 DFS 的过程中，把从 start 到 end的路径上的每个点 x 的经过次数 cnt[x]都加一。
         * 知道了每个点会被经过多少次，把 price[i]更新成 price[i]⋅cnt[i]
         * 问题就转换成计算减半后的 price[i]之和的最小值
         */
        g = new ArrayList[n];  //g[i] 是 第 i 个节点的相邻节点
        Arrays.setAll(g, e -> new ArrayList<>()); //初始化数组
        for (int[] e : edges) {
            int x = e[0], y = e[1];  //记录每个节的点相邻节点
            g[x].add(y);
            g[y].add(x);
        }

        cnt = new int[n];  //记录每个节点被经过几次
        for (int[] t : trips) {
            end = t[1]; //重置终点
            dfs(t[0], -1);
        }

        this.price = price;
        int[] res = dp(0, -1);  //递归+动态规划，暴力计算所有可能
        return Math.min(res[0], res[1]);
    }

    /**
     * 递归寻找路径
     * @param x 当前节点
     * @param father 当前节点的父节点
     * @return
     */
    private boolean dfs(int x, int father) {
        if (x == end) { // 找到 end 直接返回
            cnt[x]++;
            return true;
        }
        for (int y : g[x]) {    //遍历进入当前节点的所有子节点
            //当前节点的子节点不等于fa，就说明这个节点没有访问过
            //如果等于fa，那么这个节点就是从fa来的，防止死循环
            if (y != father && dfs(y, x)) {  //这里进入递归，判断是否有一条路径经过该节点，有则次数加一
                cnt[x]++; // x 是 end 的祖先节点，也就在路径上
                return true;
            }
        }
        return false; // 未找到 end
    }

    // 类似 337. 打家劫舍 III
    private int[] dp(int x, int father) {
        int notHalve = price[x] * cnt[x]; // x 不变
        int halve = notHalve / 2; // x 减半
        for (int y : g[x]) {
            if (y != father) {
                int[] res = dp(y, x); // 计算 y 不变/减半的最小价值总和
                notHalve += Math.min(res[0], res[1]); // x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值
                halve += res[0]; // x 减半，那么 y 只能不变
            }
        }
        return new int[]{notHalve, halve};
    }

}
